﻿class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        vector<vector<int>> ret;
        int n = nums.size();
        sort(nums.begin(), nums.end());
        int i = 0;
        for (i = 0; i < n - 3; ) {
            //三树之和
            int target_3 = target - nums[i];//三数之和目标值
            int j = 0;
            for (j = i + 1; j < n - 2; ) { //j是i的下一个 且i是动态变化的 所以j是i+1 而不是1
                int left = j + 1;
                int right = n - 1;

                long target_2 = (long)target_3 - nums[j];//两数之和目标值

                //两数之和
                while (left < right) {
                    if (nums[left] + nums[right] > target_2) {
                        right--;
                    }

                    else if (nums[left] + nums[right] < target_2) {
                        left++;
                    }

                    else {
                        ret.push_back({ nums[i], nums[j], nums[left], nums[right] });
                        left++;
                        right--;
                        while (left < right && nums[left] == nums[left - 1]) left++;
                        while (left < right && nums[right] == nums[right + 1]) right--;
                    }
                }
                //三数之和去重
                j++;
                while (j < n - 2 && i != j && nums[j] == nums[j - 1]) j++;
            }

            //四数之和去重
            i++;
            while (i < n - 3 && i != j && nums[i] == nums[i - 1]) i++;
        }
        return ret;
    }
};